#include <stdio.h>
#include <string.h>
#include <time.h>

// 简单选择排序
void simple_selection_sort(int R[], int L) {
    int m, n, k, tmp;  // m为执行趟数，n为每趟的遍历下标，tmp为交换中间变量
    for (m = 1; m < L; m++) {  // length个元素需要length-1趟
        k = m;  // 将当前趟的首个元素下标假设为最小值下标
        for (n = m + 1; n <= L; n++) {  // 循环遍历寻找更小的值
            if (R[n] < R[k]) {  // 若当前下标n的值比假设的小，则将k置为n
                k = n;
            }
        }
        if (k != m) {  // 找一圈后将遍历到的最小值和当前趟首位交换
            tmp = R[m];
            R[m] = R[k];
            R[k] = tmp;
        }
    }
}

// 打印数组
void PrintArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

// 检查数组是否已排序
int IsSorted(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        if (arr[i] < arr[i-1]) {
            return 0;  // 未排序
        }
    }
    return 1;  // 已排序
}

// 复制数组
void CopyArray(int src[], int dest[], int n) {
    for (int i = 0; i < n; i++) {
        dest[i] = src[i];
    }
}

// 测试选择排序函数
void TestSelectionSort(int original[], int n, const char* testName) {
    printf("=== %s ===\n", testName);
    printf("原始数组: ");
    PrintArray(original, n);
    
    int arr[n + 1];  
    arr[0] = 0;  // 占位符，不使用索引0
    for (int i = 1; i <= n; i++) {
        arr[i] = original[i-1];
    }
    
    simple_selection_sort(arr, n);
    printf("排序后结果: ");
    for (int i = 1; i <= n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    
    // 检查正确性（将1-based转换为0-based检查）
    int temp_check[n];
    for (int i = 0; i < n; i++) {
        temp_check[i] = arr[i + 1];
    }
    printf("排序正确性: %s\n", IsSorted(temp_check, n) ? "✓ 正确" : "✗ 错误");
    printf("\n");
}

// 主测试函数
void TestSelectionSortComprehensive() {
    printf("========== simple_selection_sort 函数测试 ==========\n\n");
    
    // 测试用例1：一般情况
    int test1[] = {64, 34, 25, 12, 22, 11, 90};
    int n1 = sizeof(test1) / sizeof(test1[0]);
    TestSelectionSort(test1, n1, "测试1：一般情况");
    
    // 测试用例2：已排序数组
    int test2[] = {1, 2, 3, 4, 5};
    int n2 = sizeof(test2) / sizeof(test2[0]);
    TestSelectionSort(test2, n2, "测试2：已排序数组");
    
    // 测试用例3：逆序数组
    int test3[] = {5, 4, 3, 2, 1};
    int n3 = sizeof(test3) / sizeof(test3[0]);
    TestSelectionSort(test3, n3, "测试3：逆序数组");
    
    // 测试用例4：重复元素
    int test4[] = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3};
    int n4 = sizeof(test4) / sizeof(test4[0]);
    TestSelectionSort(test4, n4, "测试4：重复元素");
    
    // 测试用例5：单个元素
    int test5[] = {42};
    int n5 = sizeof(test5) / sizeof(test5[0]);
    TestSelectionSort(test5, n5, "测试5：单个元素");
    
    // 测试用例6：两个元素
    int test6[] = {2, 1};
    int n6 = sizeof(test6) / sizeof(test6[0]);
    TestSelectionSort(test6, n6, "测试6：两个元素");
    
}

// 主函数
int main() {
    TestSelectionSortComprehensive();
    return 0;
}